AOJ ALDS1_5_A 総当たり
DFS ver
code:rust
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn dfs(i: usize, m: i32, a: &Vec<i32>, n: usize) -> bool {
//println!("i:{} m:{}",i,m);
if m == 0 {
return true;
}
if i >= n {
return false;
}
if m < 0 {
return false;
}
let res = dfs(i + 1, m, a, n) || dfs(i + 1, m - ai, a, n); res
}
fn main() {
let n: usize = read();
let a: Vec<i32> = (0..n).map(|_| read()).collect();
let m: usize = read();
for _x in 0..m {
println!(
"{}",
if dfs(0, read::<i32>(), &a, n) {
"yes"
} else {
"no"
}
);
}
}
bit全探索 Ver
code:rust
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
fn main() {
let n: usize = read();
let a: Vec<u64> = (0..n).map(|_| read()).collect();
for bit in 0..1 << n {
for i in 0..n {
if (bit & 1 << i) != 0 {
}
}
}
let q: usize = read();
for _ in 0..q {
let m: u64 = read();
if sum_list.iter().any(|&v| v == m) {
println!("yes");
} else {
println!("no");
}
}
}